I. Field of the Invention
The current invention relates to wireless communications. More particularly, the present invention relates to an improved method and system for reliably transmitting data through a wireless channel while minimizing the overhead inherent in the error control protocol.
II. Description of the Related Art
The use of code division multiple access (CDMA) modulation techniques is one of several techniques for facilitating communications in which a large number of system users are present. Other multiple access communication system techniques, such as time division multiple access (TDMA), frequency division multiple access (FDMA) and AM modulation schemes such as amplitude companded single sideband (ACSSB) are known in the art. These techniques have been standardized to facilitate interoperation between equipment manufactured by different companies. Code division multiple access communications systems have been standardized in the United States in Telecommunications Industry Association TIA/EIA/IS-95-B, entitled xe2x80x9cMOBILE STATION-BASE STATION COMPATIBILITY STANDARD FOR DUAL-MODE WIDEBAND SPREAD SPECTRUM CELLULAR SYSTEMSxe2x80x9d, incorporated by reference herein, and hereinafter referred to as IS-95-B.
IS-95-B was originally optimized for transmission of variable-rate voice frames. In order to support two-way voice communications, as typified in wireless phone applications, it is desirable that a communication system provide fairly constant and minimal data delay. For this reason, IS-95-B systems are designed with powerful forward error correction (FEC) protocols and vocoders which are designed to respond gracefully to voice frame errors. Error control protocols which require frame retransmission procedures add unacceptable delays to voice transmission, so are not designed into the IS-95-B specification.
The optimizations, which make the stand-alone IS-95-B specification ideal for voice applications, make it difficult to use for packet data applications. In many non-voice applications, such as the transmission of Internet protocol (IP) data, the delay requirements of the communication system are much less stringent than in voice applications. In the Transmission Control Protocol (TCP), probably the most prevalent of protocols used in an IP network, virtually infinite transmission delays are allowed in order to guarantee error-free transmission. TCP uses retransmissions of IP datagrams, as IP packets are commonly called, to provide this transport reliability.
IP datagrams are generally too large to fit into a single IS-95-B frame. Even after dividing an IP datagram into segments small enough to fit into a set of IS-95-B frames, the entire set of IS-95-B frames would have to be received without error for the single IP datagram to be useful to TCP. The targeted frame error rate typical of an IS-95-B system make the probability of error-free reception of all segments of a single datagram very low.
As described in IS-95-B, alternative service options enable the transmission of other types of data in lieu of voice frames. Telecommunications Industry Association Interim Standard TIA/EIA/IS-707-A, entitled xe2x80x9cDATA SERVICE OPTIONS FOR SPREAD SPECTRUM SYSTEMSxe2x80x9d, hereinafter referred to as IS-707, describes a set of procedures used in the transmission of packet data in an IS-95-B system.
Radio Link Protocol (RLP) is described in TIA/EIA/IS-707-A.8, entitled xe2x80x9cDATA SERVICE OPTIONS FOR SPREAD SPECTRUM SYSTEMS: RADIO LINK PROTOCOL TYPE 2xe2x80x9d, hereinafter referred to as RLP2, and incorporated herein by reference. RLP2 incorporates an error control protocol with frame retransmission procedures over the IS-95-B frame layer. RLP is of a class of error control protocols known NAK-based ARQ protocols, which are well known in the art. The IS-707 RLP, facilitates the transmission of a byte-stream, rather than a series of voice frames, through an IS-95-B communication system.
Several protocol layers typically reside above the RLP layer. IP datagrams, for example, are typically converted into a Point-To-Point Protocol (PPP) byte stream before being presented as a byte stream to the RLP protocol layer. As the RLP layer ignores the protocol and framing of higher protocol layers, the stream of data transported by RLP is said to be a xe2x80x9cfeatureless byte streamxe2x80x9d.
RLP was originally designed to satisfy the requirements of sending large datagrams through an IS-95-B channel. For example, if an IP datagram of 500 bytes were to be simply sent in IS-95-B frames carrying 20 bytes each, the IP datagram would fill 25 consecutive IS-95-B frames. Without some kind of error control layer, all 25 of these RLP frames would have to be received without error in order for the IP datagram to be useful to higher protocol layers. On an IS-95-B channel having a 1% frame error rate, the effective error rate of the IP datagram delivery would be (1xe2x88x92(0.99)25), or 22%. This is a very high error rate compared to most networks used to carry Internet Protocol traffic. RLP was designed as a link layer protocol that would decrease the error rate of IP traffic to be comparable to the error rate typical of a 10Base2 ethernet channel.
The International Telecommunications Union recently requested the submission of proposed methods for providing high rate data and high-quality speech services over wireless communication channels. A first of these proposals was issued by the Telecommunications Industry Association, entitled xe2x80x9cThe cdma2000 ITU-R RTT Candidate Submission. The Telecommunications Industry Association is currently developing the cdma2000 proposal as interim standard TIA/EIA/IS-2000, and hereinafter referred to as cdma2000. A second of these proposals was issued by the European Telecommunications Standards Institute (ETSI), entitled xe2x80x9cThe ETSI UMTS Terrestrial Radio Access (UTRA) ITU-R RTT Candidate Submissionxe2x80x9d, also known as xe2x80x9cwideband CDMAxe2x80x9d and hereinafter referred to as W-CDMA. A third proposal was submitted by U.S. TG 8/1 entitled xe2x80x9cThe UWC-136 Candidate Submissionxe2x80x9d, hereinafter referred to as EDGE. The contents of these submissions is public record and is well known in the art.
RLP2 was designed for use with IS-95-B. A new RLP designed for use with cdma2000 is described in TIA/EIA/IS-707-A-1.10, entitled xe2x80x9cDATA SERVICE OPTIONS FOR SPREAD SPECTRUM SYSTEMS: RADIO LINK PROTOCOL TYPE 3xe2x80x9d, hereinafter referred to as RLP3E, and incorporated herein by reference.
In reference to the description of the related art, two items commonly referred to as frames have the following distinction:
In IS-95-B and cdma2000, the basic timing interval is termed a frame. A frame of this variety is hereinafter referenced as a CDMA frame. A CDMA frame can contain signaling information, primary traffic, secondary traffic, or combinations thereof.
In RLP3E, the basic unit of transmission is termed a frame. A frame of this variety is hereinafter referenced as an RLP frame. An RLP frame can contain payload data, a sequence number, RLP control information (e.g. SYNC, NAK, etc.), or combinations thereof. All references to sequence numbers hereinafter are references to RLP sequence numbers.
In IS-95-B, the fundamental and supplemental channels have CDMA frames that are of a fixed 20 ms (20 millisecond) duration. CDMA frames transmitted on IS-95-B supplemental channels are transmitted at the same time that a CDMA frame is transmitted on the fundamental channel. As all IS-95-B supplemental CDMA frames are of a fixed 20 ms duration, all fundamental and supplemental CDMA frames that begin transmission at the same time will later be received by the receiver at the same time.
cdma2000 has a supplemental channel structure which differs quite significantly from that of IS-95-B. cdma2000 allows for 2 supplemental channels, hereinafter referred to as supplemental 1 and supplemental 2. During service negotiation the mobile station and the base station negotiate a configuration, part of which is the supplemental channel CDMA frame duration(s). The durations that can be negotiated for each supplemental channel are: 20 ms, 40 ms, and 80 ms. It is conceivable, that in the future, durations could include alternate or additional values, such as 60 ms. If a 60 ms CDMA frame length never comes into existence, it in no way detracts from the need nor the value of the present invention. However, because a value of 60 ms is conceivable, and the present invention takes into account durations that, are not presently utilized in cdma2000, various scenarios are presented throughout this specification which assume the existence of a 60 ms CDMA frame duration.
As the amount of data that can be transmitted in a channel is related to the CDMA frame duration, hereinafter CDMA frame durations are referenced as CDMA frame lengths. cdma2000 allows the negotiated configuration to be one in which the CDMA frame length for supplemental 2 is different than the CDMA frame length for supplemental 1. Any telecommunications system that supports the concurrent transmission of data packets on different code channels from one entity, such as a cdma2000 base station, capable of transmitting user data on a fundamental and supplemental channel(s) concurrently, to another entity, such as a cdma2000 mobile, is hereafter referenced as a cdma2000-like system.
In RLP2, RLP3E, and all existing RLP implementations, three variables are maintained at either side of an RLP protocol link. These variables are V(R), V(N) and V(S). As discussed in the RLP standards, V(R) contains the expected value of the RLP frame sequence number field in the next new frame to be received. V(N) contains the sequence number of the next needed frame not received in sequence. The sequence number field xe2x80x98SEQxe2x80x99 in each new RLP data frame sent, and in each RLP idle frame sent, shall be set to V(S). Each of the variables V(R), V(N), and V(S), are the shortened (8-bit), over-the-air versions of the full (12-bit) sequence numbers L_V(R), L_V(N) and L_V(S) also maintained at either side of an RLP protocol link.
RLP2 and all other RLPs are essentially designed as state machines called from the multiplex sublayer every 20 ms. At each 20 ms interval, the multiplex sublayer delivers to RLP a set of frames received from the physical layer. Each time the multiplex sublayer delivers a set of frames to the RLP state machine, also known as the RLP engine, the RLP state machine compares the sequence number(s) of the just received frames to L_V(R) and L_V(N). In the event that RLP finds a new xe2x80x98holexe2x80x99 was created, a NAK is generated. The term xe2x80x98holexe2x80x99 is commonly used by those skilled in the art to denote that a set frames containing non-consecutive sequence numbers was received by the RLP3E engine. A xe2x80x98new holexe2x80x99 is created whenever the updated L_V(R) is different from the previous L_V(R), and all frames received with sequence numbers greater than the previous L_V(R) do not have consecutive sequence numbers.
RLP3E is similar to RLP2 in many respects. In part, this was done to gain the many benefits that code reuse can provide. RLP3E was designed, as was RLP2, to associate a frame sequence number with each RLP frame transmitted and received. Whenever an unexpected sequence number is received, a request for retransmission, referred to as a NAK, is sent to the peer RLP entity.
No unnecessary retransmissions are generated In RLP2 because all IS-95-B CDMA frames transmitted at the same time are received by the receiver at the same time. If an RLP2 state machine finds that a hole has been created by the receipt of a 20 ms set of frames from the multiplex sublayer, due to the simultaneous transmission of all frames on the supplemental channels, it means that the frames in the hole have been lost or corrupted in route to the receiver. As such a NAK generated for such a hole is not unnecessary, as the retransmission of the frames in the hole are desirable. Utilizing the same methodology, however, causes RLP3E to generate unnecessary retransmissions because of the flexible nature of the cdma2000 supplemental channels. This is because, as described earlier, it is possible in cdma2000 for supplemental channels to vary in CDMA frame length. Such variations can unintentionally cause RLP3E to detect holes and cause the generation of unnecessary NAKs.
For example, FIG. 1A shows a 160 ms time interval of generated RLP data frames for an RLP3E data call in which there are a fundamental channel and two supplemental channels. As illustrated, supplemental 1 has a CDMA frame length of 80 ms, supplemental 2 has a CDMA frame length of 60 ms, and the RLP sequence number at the beginning of this time interval is 5. At time 0 the multiplex sublayer asks the RLP engine for three frames of lengths corresponding to the frame duration of the fundamental channel and each supplemental channel. In response, the RLP engine generates three RLP frames having sequence numbers 5, 6, and 7. At the 20 ms boundary the RLP frame having sequence number 8 is generated in response to the multiplex sublayer asking for a single frame of a length corresponding to the fundamental channel. At the 40 ms boundary an RLP frame containing sequence number 9 is generated. At the 60 ms boundary the multiplex sublayer asks for frames of lengths corresponding to the fundamental channel and supplemental 2. In response, the RLP engine generates two RLP frames having sequence numbers 10 and 11. Likewise, RLP frames with sequence numbers 12 and 13 are generated at the 80 ms boundary for like reasons. Frames 14-17 are generated for like reasons at the times illustrated in FIG. 1A.
The receipt of the aforementioned frames by the receiving RLP3E engine is illustrated in FIG. 1B. FIG. 1B does not show the length/duration of the received frames, as is done in FIG. 1A. Rather, FIG. 1B shows the time at which the frame is given to the RLP3E receive engine from the receiving multiplex sublayer. FIG. 1B assumes there is zero delay from the time the frame transmission completed in FIG. 1A to the time that the RLP3E receive engine has the frame delivered to it by the multiplex sublayer. For example, because the transmission of frame 5 finishes at time 20 ms in FIG. 1A, it is received by the RLP3E receive engine at time 20 ms in FIG. 1B. Because the transmissions of frames 7 and 9 complete at 60 ms in FIG. 1A, they are received for processing by the RLP3E engine at 60 ms in FIG. 1B. Likewise, because the transmissions of frames 6 and 10 complete at time 80 ms in FIG. 1A, these frames are received for processing by the RLP3E receive engine at time 80 ms in FIG. 1B. The receipt of frame 8, and frames 11 through 17, are diagrammed in a similar manner.
As is evident by comparison of the figures, RLP frames transmitted with ordered incremental sequence numbers are not received in order by the receiving RLP engine. Although the frames began transmission in the same sequence that the RLP3E generated the sequence numbers in, the frames were received in a different order. Namely, CDMA frames containing RLP sequence numbers 5 through 17 were transmitted in the following order 5,6,7,8,9,10,11,12,13,14,15,16,17, yet were received in the order of 5,8,7,9,6,10,12,11,14,15,13,17,16 owing to the differences in frame duration. As would be evident to one skilled in the art, NAKs would be generated for frames 6,7,11,13, and 16 due to the timing and order at which frames 8, 12, 14, and 17 were received.
As one skilled in the art is aware, the generation of NAKs should only be done when the receiver failed to receive a transmission of an RLP data frame that it should have already received. However, due to the varying CDMA frame lengths of cdma2000, unnecessary NAKs can be generated due to the timing at which sequence numbers are received. This causes the undesirable effect of wasting valuable bandwidth both on the forward and reverse links. The bandwidth is wasted by each NAK transmitted on one link and by the unnecessary retransmitted data frame on the opposite link (an unnecessary retransmitted data frame is generated for each received unnecessary NAK).
As over-the-air bandwidth is a valuable resource, an improved method of delivering data over cdma2000 is desirable. In particular, a method for delivering data over cdma2000 that doesn""t generate unnecessary NAKs and retransmissions is highly desirable. It is desirable that such a method neither increases the latency of the delivery of data frames to the layer above RLP nor increases the latency of the delivery of valid NAK frames to the multiplex sublayer. It is particularly desirable that such a method leverage existing work by requiring minimal changes to existing implementations of RLP3E.
The present invention is a novel and improved method and system that prevents RLP3E from generating unnecessary NAKs, thus also preventing unnecessary data frame retransmissions. The present invention is efficient, neither delaying the delivery of data frames to the higher data services layer, nor delaying the delivery of necessary NAKs to the multiplex sublayer. Additionally, the present invention can be implemented with minimal changes to an existing RLP3E implementation. The present invention is applicable to systems such as cdma2000, W-CDMA, and EDGE, wherein data is transferred using an ARQ (automatic request for retransmission) mechanism, and wherein data packets are sometimes received in an order different from that in which they were transmitted.
In relation to the transmission and receipt of RLP frames, RLP3E currently communicates with a multiplex sublayer below it and a byte stream layer above it. The byte stream layer is commonly referred to as the PPP layer, because PPP is commonly the protocol used in the byte stream layer. However, as the byte stream layer need not be PPP (it could be ISDN, or one of a plurality of protocols), it is herein referred to as the byte stream layer. The aforementioned communication flow is illustrated in FIG. 2, a block diagram showing the data path for cdma2000.
The present invention utilizes a new mechanism interposed between the multiplex sublayer and the RLP3E layer for all incoming traffic. The purpose of this sublayer is to reorder the received packets into the order in which they were transmitted, and to deliver the packets to the RLP3E layer in said order. This sublayer is hereafter called the frame reordering sublayer, and, is illustrated as such in FIG. 3.
The frame reordering sublayer reorders frames received by the multiplex sublayer by determining the order in which physical layer frames were transmitted by its peer, and by buffering each received frame until all frames transmitted prior to it have been received. The frame reordering sublayer accomplishes this by means of timers and/or frame counters, and a memory buffering mechanism.